class Solution:
    def longestIncreasingPath(self, matrix):
        if not matrix: return 0
        nRow = len(matrix)
        nCol = len(matrix[0])
        dp = [[None for _ in range(nCol)] for _ in range(nRow)]

        def find(r, c):
            if dp[r][c]==None:
                path = 1
                # up
                if r-1>=0 and matrix[r-1][c]>matrix[r][c]:
                    path = max(path, find(r-1,c)+1)
                # down
                if r+1<nRow and matrix[r+1][c]>matrix[r][c]:
                    path = max(path, find(r+1,c)+1)
                # left
                if c-1>=0 and matrix[r][c-1]>matrix[r][c]:
                    path = max(path, find(r,c-1)+1)
                # right
                if c+1<nCol and matrix[r][c+1]>matrix[r][c]:
                    path = max(path, find(r,c+1)+1)
                dp[r][c] = path
            return dp[r][c]
        
        for r in range(nRow):
            for c in range(nCol):
                find(r,c)
        return max(map(max, dp))

print(Solution().longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))